The present invention relates to halftone reproduction of graphic images which are commonly in a bitmap format.
Image information is commonly generated in a bitmap format where the bitmap comprises a plurality of "gray" level cells (or hue concentration level cells for color images). Each cell consists of a two-dimensional array of pixels, or cell elements, and the gray or hue level to be created in each cell is defined by digital values, wherein each digital value represents a gray or hue concentration level among a number of gray or hue concentration levels within the area. Thus, if a cell is composed of 25 pixels, there are 26 levels of gray or hue concentration, varying incrementally between black (or a solid color) and white.
One standard method of converting gray or hue concentration level image data into binary level pixel image data is through the use of dithering or halftoning processes. In such methods, over a given area having a number of gray or hue concentration level cells therein, each pixel of a cell is compared to one of a set of pre-selected thresholds. Each such cell represents a "halftone cell". The effect of such an arrangement is that, for an area where the image is gray or some shade of a hue, some of the thresholds within the halftone cell will be exceeded, while others are not.
In the monochrome case, the pixels or cell elements for which thresholds are exceeded are printed as black or a selected primary color, while the remaining cell elements are allowed to remain white. The human eye integrates the distribution of white and black, or the selected color, over the cell as gray. In this manner, there can be gradual transitions between different shades of gray or the selected color among adjacent halftone cells.
For full or plural color applications, several halftone cells, each corresponding to a different hue, are formed for a given area. The color system superimposes the halftone cells of different hues to form the desired color of the image. Halftoning facilitates varying the concentration or intensity level of hues within the color image by varying the number of darkened pixels for halftone cells corresponding to particular hues. In this manner, the image can have transitions between neighboring colors among adjacent halftone cells. The application of halftoning to color systems is described in detail in the Postscript Reference Manual published by Adobe.
Unfortunately, in using a halftoning technique, there is often a trade-off between maximizing the number of gray or hue concentration levels and the sharpness of the image; the larger each cell is (to contain more pixels), the fewer cells will fit into a given area. Fewer cells within a given area effectively decreases sharpness. This gray or hue concentration level/sharpness trade-off often forces product designers to choose between reproducing an image using many gray levels but in large halftone dots (resulting in coarse, grainy images) or using fine halftone dots but only a few gray or hue concentration levels (which can cause heavy banding). The effects of banding are illustrated described in my U.S. Pat. No. 5,587,81 1, which issued on Dec. 24, 1996, particular reference being made herein to FIG. 1 and the accompanying description in that patent. Banding results from a noticeable jump in the gray levels between adjacent regions.
Some techniques have been developed to address this trade-off between gray levels and sharpness in an attempt to maximize sharpness while minimizing the effects of banding. Xerox Corporation developed a technique called Quad Dot. It is believed that the Quad Dot technique divides a halftone cell into four smaller cells.
The Quad Dot system attempts to distribute darkened pixels among the smaller cells. However, it is believed that the Quad Dot system sequentially adds pixels to adjacent smaller cells in a deterministic circular fashion about the center of the larger cell. This can result in a noticeable pattern within the image.
The above-cited U.S. Pat. No. 5,587,811 addresses certain of the shortcomings of these prior art methods and systems by providing a method and apparatus for halftoning which utilizes a macro halftone cell defining an area of contiguous pixels. The method and apparatus partition the macro halftone cell into a plurality of sub-halftone cells, each sub-halftone cell defining an area of contiguous pixels. A predetermined level of desired grayness or hue intensity determines the quantity of pixels to be darkened within the macro halftone cell. In accordance with one aspect of this method and apparatus, a spot function ranks pixels within the macro halftone cell from highest to lowest such that preferably one or more of the following design rules apply: no two pixels within the same sub-halftone cell are ranked consecutively; and the rank of each individual pixel within each sub-halftone cell is a decreasing function of the distance between the center of the sub-halftone cell and the center of the pixel (e.g., a pixel closest to the center of the sub-halftone cell has the highest rank of pixels within the sub-halftone cell and a pixel furthest from the center of the sub-halftone cell has the lowest rank of pixels within the sub-halftone cell) and the number of pixels ranked above any particular pixel within the sub-halftone cell is no more than one greater and no more than one less than the number of pixels ranked above the particular pixel in any other sub-halftone cell within the macro halftone cell. Each pixel having a rank higher than or equal to a threshold ranking is darkened, wherein the threshold ranking is set so that the determined quantity of pixels is darkened. Such an arrangement has been found to provide an even distribution of darkened pixels among the halftone cells of the macro halftone cell yet maintain a high level of resolution.
In accordance with another aspect of the invention disclosed in U.S. Pat. No. 5,587,811, the macro halftone is partitioned into an area of v by w contiguous sub-halftone cells where v and w are odd positive integers. Having a macro halftone cell of odd dimensions of sub-halftone cells can define exactly one center sub-halftone cell. This facilitates a balanced distribution of sub-halftone spots within the macro halftone cell to provide a balanced image across the macro halftone cell.
By altering the distribution of darkened pixels within the halftone cell for a desired level of grayness, a more balanced image in black and can be produced. Maintaining high resolution and the large number of levels of hue concentration within the macro halftone in color printers provides a smooth transition to neighbor colors and a well balanced in-gamut distribution.
While the method and system disclosed in the above-cited patent do produce image quality improvement, they nevertheless possess certain shortcomings. For example, the transition which they exhibit from one intensity, or darkness, level to the next does not ideal smoothness across a macro halftone cell and they do not permit a gamma correction to be made in an acceptably simple manner. Gamma correction involves a correction for the difference between the percentage of dots in a cell which are darkened and the apparent darkness of that cell. It has been found that over the range of possible darkness values, a cell will generally appear to have a darkness greater than the percentage of dark pixels within the cell. For example, at about the midpoint between the lightest and the darkest levels, when 50% of the pixels in the cell are dark, the average observer will consider the cell to have a darkness of the order of 70%.